//Given an integer array nums sorted in non-decreasing order, return an array 
//of the squares of each number sorted in non-decreasing order. 
//
// 
// Example 1: 
//
// 
//Input: nums = [-4,-1,0,3,10]
//Output: [0,1,9,16,100]
//Explanation: After squaring, the array becomes [16,1,0,9,100].
//After sorting, it becomes [0,1,9,16,100].
// 
//
// Example 2: 
//
// 
//Input: nums = [-7,-3,2,3,11]
//Output: [4,9,9,49,121]
// 
//
// 
// Constraints: 
//
// 
// 1 <= nums.length <= 10⁴ 
// -10⁴ <= nums[i] <= 10⁴ 
// nums is sorted in non-decreasing order. 
// 
//
// 
//Follow up: Squaring each element and sorting the new array is very trivial, 
//could you find an O(n) solution using a different approach? Related Topics Array 
//Two Pointers Sorting 👍 4133 👎 140


package leetcode.editor.en;

import java.time.OffsetDateTime;

public class _977_SquaresOfASortedArray {
    public static void main(String[] args) {
        Solution solution = new _977_SquaresOfASortedArray().new Solution();
        int[] ints = solution.sortedSquares1(new int[]{-7,-3,2,3,11});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int[] left;
        public int[] sortedSquares2(int[] nums) {
            int resultLent = nums.length-1, r = nums.length-1;
            int[] result = new int[nums.length];
            for (int i = 0; i <=r; ) {
                if (nums[i]*nums[i] > nums[r]*nums[r]){
                    result[resultLent--] = nums[i]*nums[i];
                    i++;
                }else {
                    result[resultLent--] = nums[r]*nums[r];
                    r--;
                }
            }
            return result;
        }


        public int[] sortedSquares1(int[] nums) {
            int[] result = new int[nums.length];
            int r = nums.length-1, j = nums.length-1;
            for (int i = 0; i <= r;) {
                if (nums[i] * nums[i]>nums[r]*nums[r]){
                    result[j--] = nums[i]*nums[i];
                    i++;
                }else {
                    result[j--] = nums[r]*nums[r];
                    r--;
                }
            }
            return result;
        }
        public int[] sortedSquares(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                nums[i] = nums[i]*nums[i];
            }
//            left = new int[nums.length/2];
//            mergeSort(nums, 0, nums.length);
            quickSort(nums, 0, nums.length);
            return nums;
        }

        private void quickSort(int[] nums, int begin, int end) {
            if (end - begin<2) {
                return;
            }
            int pivot = getPivot(nums, begin, end);
            quickSort(nums, begin, pivot);
            quickSort(nums, pivot+1, end);
        }

        private int getPivot(int[] nums, int begin, int end) {
            int pivot = nums[begin];
            end--;
            while (begin<end){
                while (begin<end){
                    if (nums[end]<pivot){
                        nums[begin++] = nums[end];
                        break;
                    }else {
                        end--;
                    }
                }
                while (begin<end){
                    if (nums[begin]>pivot) {
                        nums[end--] = nums[begin];
                        break;
                    }else {
                        begin++;
                    }
                }
            }
            nums[begin] = pivot;
            return begin;
        }

        private void mergeSort(int[] nums, int start, int end) {
            if (end - start<2) {
                return;
            }
            int mid = start + (end - start) / 2;
            mergeSort(nums, start, mid);
            mergeSort(nums, mid, end);
            doMerge(nums, start, mid, end);
        }

        private void doMerge(int[] nums, int start, int mid, int end) {
            int li = 0, le = mid -start;
            int ri = mid, re = end;
            int ai = start;
            for (int i = 0; i < le; i++) {
                left[i] = nums[start+i];
            }
            while (li<le){
                if (ri<re && left[li]>nums[ri]) {
                    nums[ai++] = nums[ri++];
                }else {
                    nums[ai++] = left[li++];
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}